Secure digital signing and verification are often used in e-commerce, messaging, and product verification to authenticate the source of a binary object. Digital signatures schemes have been created that require a small amount of computing power to compute a signature, but a significantly greater amount of computing power to impersonate a signor of a given message. However, as computing power increases, the safety of prior digital signature algorithms is jeopardized, and new algorithms must be implemented to secure the identity of binary objects. In addition, with the advent of mobile computing devices in which computational power and battery life are at a premium, there is an increasing need for efficient and secure message signing and verification methods.
Digital encryption and decryption are similarly necessary to secure communications and transactions over electronic medium. Encryption of a digital message ensures that only the intended recipient may decrypt and read the contents of the message. For example, in asymmetric key cryptography, a message may be encrypted with a public key such that the private key corresponding to the public key is needed to decrypt the message. Thus, only the holder private key will be able to access the message.
There is an ever-increasing need to implement a variety of signature and encryption schemes, both to reduce the computational overhead necessary to perform these cryptographic functions, and to create a diverse set of signature and encryption schemes to mitigate the risk of a single scheme being broken.
One type of signature scheme currently known utilizes elliptic curves defined over a finite field. One example is the Boneh-Lynn-Schacham (BLS) signature scheme, which utilizes a single curve to sign a message. The BLS signature scheme generates two points P & Q on the curve. P is calculated by using a hashing function to hash the message onto the curve. Q is selected, possibly at random, on the curve. The signor multiplies some secret S, which is an integer of large prime degree, with the point Q to create the signature. The signor also creates a public key by multiplying the secret S by the hash of the message. P, Q, the signature, and the public key are made available for anyone to use, but the secret S is not made public.
A recipient of the message may verify the authenticity of the signor by verifying that the signature equals S times the hash of the message. This comparison is accomplished by evaluating two bilinear Weil pairings and checking for equality.